package com.xw.class04;/**
*  @author: xw
*  @create: 2022/9/15 11:20
*  @description: 归并排序
*/
public class Code01_MergeSort {
    // 递归方法实现
    public static void mergeSort1(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }


    private static void process(int[] arr, int left, int right) {
        if(left == right){
            return ;
        }
        int mid = left + ((right - left)>>1);
        process(arr,left,mid);
        process(arr,mid+1,right);
        merge(arr,left,mid,right);
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int[] help = new int[right - left +1];
        int i = 0;
        int p1 = left;
        int p2 = mid +1;

        //当左边指针和右边指针都不超出范围时，添加元素的方式
        while (p1 <= mid && p2 <= right){
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        //指针越界只会出现要么p1越界要么p2越界
        while (p1 <= mid){
            help[i++] = arr[p1++];
        }
        while (p2 <= right){
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++) {
            arr[left + i] = help[i];
        }
    }
    public static void merge02(int[] arr){
        if(null == arr || arr.length < 2){
            return;
        }

        int n = arr.length;
        int mergeSize = 1;
        while(mergeSize<n ){
            int left = 0;
            while(left < n){
                if(mergeSize > n - left ){
                    break;
                }
                int mid = left + mergeSize -1;
                int right = mid + Math.min(mergeSize,n - mid -1);
                merge(arr,left,mid,right);
                left = right + 1;
            }
            // 防止溢出
            if (mergeSize > n / 2) {
                break;
            }
            mergeSize <<= 1;
        }
    }
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] ints = {9, 2, 4, 1, 7, 5, 19, 5, 1, 7, 20, 35, 3, 77};
        mergeSort1(ints);
        printArray(ints);
    }
}
